package main.Q501_600;

import java.util.LinkedList;
import java.util.Queue;

public class Q541_550 {
    public static void main(String[] args) {
        System.out.println("Question541：反转字符串Ⅱ");
        System.out.println("Question542：01矩阵");
        System.out.println("Question543：二叉树的直径");
        System.out.println("Question544：");
        System.out.println("Question545：");
        System.out.println("Question546：");
        System.out.println("Question547：省份数量");
        System.out.println("Question548：");
        System.out.println("Question549：");
        System.out.println("Question550：");
    }
}

class Question541 {
    public String reverseStr(String s, int k) {
        int i = 0;
        StringBuffer result = new StringBuffer();
        for (i = 0; i < s.length() / (2 * k); i++) {
            StringBuffer temp = new StringBuffer(s.substring(i * 2 * k, i * 2 * k + k));//取每2k的前k个
            result.append(temp.reverse());//反转的内容
            result.append(s.substring(i * 2 * k + k, i * 2 * k + 2 * k));//为反转的内容
        }
        StringBuffer temp = new StringBuffer(s.substring(i * 2 * k, s.length()));
        if (temp.length() <= k) {
            result.append(temp.reverse());
        } else {
            result.append(new StringBuffer(temp.substring(0, k)).reverse());
            result.append(temp.substring(k, temp.length()));
        }
        return result.toString();
    }
}

class Question542 {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length, col = mat[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();// 用于存入处理的点
        for (int i = 0; i < row; i++) {// 先找到0的点位
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            if (i != 0 && mat[i - 1][j] == -1) {// 上面
                mat[i - 1][j] = mat[i][j] + 1;
                queue.add(new int[]{i - 1, j});
            }
            if (j != 0 && mat[i][j - 1] == -1) {// 左侧
                mat[i][j - 1] = mat[i][j] + 1;
                queue.add(new int[]{i, j - 1});
            }
            if (j != col - 1 && mat[i][j + 1] == -1) {// 右侧
                mat[i][j + 1] = mat[i][j] + 1;
                queue.add(new int[]{i, j + 1});
            }
            if (i != row - 1 && mat[i + 1][j] == -1) {// 下侧
                mat[i + 1][j] = mat[i][j] + 1;
                queue.add(new int[]{i + 1, j});
            }
        }
        return mat;
    }
}

class Question543 {
    //    public class Info{
//        public int maxLength;//记录单侧最长长度
//        public int totalLength;//记录节点两侧最远节点距离(即是左右子树单侧最长相加)
//        public Info(int max,int total){
//            this.maxLength=max;
//            this.totalLength=total;
//        }
//    }
//    public Info process(TreeNode root,TreeNode head){
//        if (root==null) return new Info(0,0);
//        Info left=process(root.left,head);
//        Info right=process(root.right,head);
//        int totalLength=0;
//        int maxLength= left.maxLength > right.maxLength ? left.maxLength+1 : right.maxLength+1;//该节点单边最长距离
//        int tempMaxTotal=left.totalLength> right.totalLength? left.totalLength : right.totalLength;//左右子树中最远距离
//        if (left.maxLength+ right.maxLength>=tempMaxTotal) totalLength=left.maxLength+ right.maxLength;//该子树最大距离
//        else totalLength=tempMaxTotal;
//        return new Info(maxLength,totalLength);
//
//    }
//    public int diameterOfBinaryTree(TreeNode root) {
//        Info result=process(root,root);
//        return result.totalLength;
//    }
    int result = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        process(root);// 单侧肯定比双侧短
        return result;
    }

    public int process(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = process(root.left);
        int right = process(root.right);
        result = Math.max(left + right, result);
        return Math.max(left, right) + 1;
    }
}

class Question547 {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visited = new boolean[cities];
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                process(isConnected, visited, cities, i);
                provinces++;
            }
        }
        return provinces;
    }

    public void process(int[][] isConnected, boolean[] visited, int cities, int i) {
        for (int j = 0; j < cities; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                process(isConnected, visited, cities, j);
            }
        }
    }
}